package offer;

import java.util.Arrays;

public class 最小的k个数40 {

    public static void main(String[] args) {

    }

    //解题思路：
    //一、用快排最最最高效解决 TopK 问题：
    //二、大根堆(前 K 小) / 小根堆（前 K 大),Java中有现成的 PriorityQueue，实现起来最简单：


    // 一、快排记模板
    // 题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求, 只需要将数组划分为 最小的 kk 个数 和 其他数字 两部分即可
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }

        if (k >= arr.length) {
            return arr;
        }
        // quick_sort() 的功能不是排序整个数组，而是搜索并返回最小的 kk 个数
        return quickSort(arr, k, 0, arr.length - 1);
    }

    // TODO
    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) {
                j--;
            }
            while (i < j && arr[i] <= arr[l]) {
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, i, l);
        if (i > k) {
            return quickSort(arr, k, l, i - 1);
        }
        if (i < k) {
            return quickSort(arr, k, i + 1, r);
        }
        return Arrays.copyOf(arr, k);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    // 二 大根堆 O(NlogK)
    // 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
    // 1. 若目前堆的大小小于K，将当前数字放入堆中。
    // 2. 否则判断当前数字与大根堆堆顶元素的大小关系，
    // 如果当前数字比大根堆堆顶还大，这个数就直接跳过；
    // 反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
//    public int[] getLeastNumbers(int[] arr, int k) {
//        if (k == 0 || arr.length == 0) {
//            return new int[0];
//        }
//
//        // 默认是小根堆，实现大根堆需要重写一下比较器。
//        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
//        for (int num : arr) {
//            if (pq.size() < k) {
//                pq.offer(num);
//                //当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中
//            } else if (num < pq.peek()) {
//                pq.poll();
//                pq.offer(num);
//            }
//            // 如果当前数字比大根堆堆顶还大，直接跳过
//        }
//
//        // 返回堆中的元素，queue转数组
//        int[] res = new int[pq.size()];
//        int idx = 0;
//        for (int num : pq) {
//            res[idx++] = num;
//        }
//        return res;
//    }
}
